package LeetCode.leetcode257;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(6);
        root.left = node1;
        root.right = node2;
        node1.right = node3;
        node2.left = node4;
        List<String> res = binaryTreePaths(root);
        System.out.println(res.toString());


    }

    public static List<String> binaryTreePaths(TreeNode root) {
        if (root == null)
            return null;
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        List<TreeNode> child = new ArrayList<>();
        //添加当前节点
        sb.append(root.val);
        sb.append("->");
        //构造children
        if (root.left == null && root.right != null) {
            child.add(root.right);
        } else if (root.right == null && root.left != null) {
            child.add(root.left);
        } else {
            child.add(root.left);
            child.add(root.right);
        }
        backTracking(sb, root, res, child);
        return res;
    }

    public static void backTracking(StringBuilder path, TreeNode curNode, List<String> res, List<TreeNode> children) {
        //递归结束条件
        if (curNode.left == null && curNode.right == null) {
            res.add(new String(path.substring(0, path.length() - 2)));
            return;
        }
        for (int i = 0; i < children.size(); i++) {
            List<TreeNode> child = new ArrayList<>();
            path.append(children.get(i).val);
            path.append("->");
            //构造children
            if (children.get(i).left == null && children.get(i).right != null) {
                child.add(children.get(i).right);
            } else if (children.get(i).left == null && children.get(i).right == null) {
                //不做事
            } else if (children.get(i).right == null && children.get(i).left != null) {
                child.add(children.get(i).left);
            } else {
                child.add(children.get(i).left);
                child.add(children.get(i).right);
            }
            //递归
            backTracking(path, children.get(i), res, child);
            //回溯
            path.delete(path.length() - 3, path.length());
        }
    }
}
